package chapter04;
//kmp算法
public class test04_kmp{
    /**
     * 用于计算匹配的位置（从头到尾）
     * @param str 主串
     * @param sub 模式串
     * @return
     */
    public static int kmp(String str, String sub) {
        int i = 0,j = 0;
        int[] next = getNext(sub);
        while (i < str.length() && j < sub.length()){
            if(j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if(j == sub.length())
            return i-j;
        else
            return -1;
    }

    /**
     * 用于生成部分匹配表next
     * @param sub 模式串
     * @return
     */
    private static int[] getNext(String sub) {
        int[] next = new int[sub.length()+1];
        int i = 0, j = -1;
        next[0] = -1;
        while(i<sub.length()){
            if (j==-1 || sub.charAt(i) == sub.charAt(j)){
                next[++i] = ++j;
            }else {
                j = next[j];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        int res = test04_kmp.kmp("abababbcabca","ababbca");
        if (res==-1){
            System.out.println("匹配失败");
        }else {
            System.out.println("匹配位置为"+res);
        }
    }
}
